import java.util.HashMap;

public class L76 {

    public static void main(String[] args) {
        String s = "cabwefgewcwaefgcf";
        String t = "cae";
        String s1 = new Solution().minWindow(s, t);
        System.out.println(s1);


    }


    static class Solution {
        public String minWindow(String s, String t) {
            int si = 0;
            int valid = 0;
            int minLen = Integer.MAX_VALUE;
            int start= 0;

            HashMap<Character, Integer> tMap = new HashMap<>(t.length());
            HashMap<Character, Integer> window = new HashMap<>(t.length());

            // 先把t的数据统计出来
            for (int tj = 0; tj < t.length(); tj++) {
                tMap.put(t.charAt(tj), tMap.getOrDefault(t.charAt(tj), 0) + 1);
            }


            for (int sj = 0; sj < s.length(); sj++) {
                char r = s.charAt(sj);

                if (tMap.containsKey(r)) {
                    window.put(r, window.getOrDefault(r, 0) + 1);
                    if (tMap.get(r).equals(window.get(r))) {
                        valid++;
                    }
                }

                // 窗口内字符完全包含需求t中字符
                while (valid == tMap.size()) {
                    if (sj - si < minLen) {
                        minLen = sj - si + 1;
                        start = si;
                    }
                    char c = s.charAt(si);
                    if (tMap.containsKey(c)) {
                        window.put(c, window.get(c) - 1);
                        if (window.get(c) < tMap.get(c)) {
                            valid--;
                        }
                    }
                    si++;
                }
            }
            return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
        }
    }
}
